package main

import (
	"log"
)

// 在 纵横 有序 排列的二维数组中 查找某个数

func main() {
	list := []int{1, 3, 4, 6, 8, 9, 12, 34, 44, 45}
	log.Println(binaryFind(list, 35))

	slice := [][]int{
		{1, 3, 5, 4, 7, 9},
		{2, 4, 6, 8, 10, 11},
		{12, 13, 14, 15, 16, 17},
		{18, 19, 20, 21, 22, 23},
		{24, 25, 26, 27, 28, 29},
		{30, 31, 32, 33, 34, 46},
	}
	log.Println(" 最终结果=", TwoSliceFind(slice, 46))
}

//在一个二维数组中（每个一维数组的长度相同）
//每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，
//输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

func TwoSliceFind(data [][]int, target int) []int {

	var temp int
	for i := 0; i < len(data); {
		for j := len(data[i]) - 1; j >= 0; {
			temp = data[i][j]
			if temp == target {
				return []int{i, j}
			}
			if temp > target {
				if j == 0 {
					return []int{}
				}
				j--
				// 继续搜索该行下一个元素
				continue
			}
			if temp < target {
				if i == len(data) {
					return []int{}
				}
				i++
				// 跳转到下一行搜索
				break
			}
		}
	}
	return []int{}
}

func binarySliceFindPlus(list [][]int, target int) bool {
	for i := 0; i < len(list); {
		if list[i][0] > target || list[i][len(list[i])-1] < target {
			i++
			continue
		}
		exist, _ := binaryFind(list[i], target)
		if exist {
			return true
		} else {
			i++
		}
	}
	return false
}

func binarySliceFind(list [][]int, target int) bool {
	var exist = false
	startIndex, endIndex := 0, len(list[0])-1
	lastIndex := 0
	for i := 0; i < len(list); i++ {
		currentList := list[i][startIndex : endIndex+1]
		log.Println("遍历开始i=", i, "currentList =", currentList, " startIndex=", startIndex, " endIndex=", endIndex)
		exist, lastIndex = binaryFind(currentList, target)
		if exist {
			return exist
		}
		lastIndex = startIndex + lastIndex
		if lastIndex == startIndex {
			return false
		}
		if lastIndex == endIndex {
			if currentList[lastIndex] > target {
				endIndex = lastIndex - 1
			}
			if currentList[lastIndex] < target && i <= len(list)-1 {
				if list[i+1][lastIndex] == target {
					return true
				}
				if list[i+1][lastIndex] < target {
					i++
				}
			}
		}
		if lastIndex < endIndex {
			endIndex = lastIndex - 1
		}
	}

	return exist
}

func binaryFind(list []int, target int) (bool, int) {
	if len(list) == 0 {
		return false, 0
	}
	pivot := 0
	left, right := 0, len(list)-1
	for left <= right {
		if len(list)/2 == 0 {
			pivot = right - (right-left)>>1
		} else {
			pivot = left + (right-left)>>1
		}
		if list[pivot] == target {
			return true, pivot
		}
		if list[pivot] > target {
			right = pivot - 1
		} else {
			left = pivot + 1
		}

	}
	return false, pivot
}
